Понятная информатика,

Формальные описания реальных процессов и объектов (ОГЭ, задание 4)

Есть вопросы и замечания - пишите!

В основу данного занятия положен курс из учебника:  А.Г.Кушниренко и др. Информатика, 9 класс. М., «Дрофа», 2018 год.

 

Перед решением данного задания нужно вспомнить, что такое графические информационные модели и табличные информационные модели.

 

На рис.1  представлен фрагмент схемы дорог Московской области. В математике подобные схемы называют графами, линии на них – ребрами графов, а точки – вершинами графа.

 

Есть разные определения графа, будем использовать простейшее из них.

 

Граф – это непустое конечное множество вершин и конечное множество пар различных вершин.

 

Согласно формальному определению, ребром называю пару вершин графа. Неформально ребро изображают линией, соединяющей пару вершин (вершина в графе не может быть соединена сама с собой!). Эту линию

также называют ребром. Таким образом, можно сказать, что ребро соединяет две вершины графа, или что вершины графа соединены ребром.

 

Графы называется неориентированными, если для любого ребра не указывается, какая вершина начальная, а какая – конечная. Примером такого графа может служить схема дорог с двусторонним движением. Ребрами в этом графе служат пары городов, соединенных дорогами. Если два города А и В (две вершины графа) соединены дорогой (образуют ребро графа), то можно проехать как из А в В, так и из В в А. Поэтому такой ребро можно задать как (А,В)  и как (В,А).

 

Вершины, соединенные графами, называются соседними. Количество ребер, выходящих из вершины (то есть вершин, соседних с ней), называются степенью вершины. 

 

Например, на рис.2 представлен граф, у которого пять вершин (A, B, C, D, E) и пять ребер (AB, AD, BC, BD, DE). Вершина А соседняя с вершинами B и D, но не соседняя с С и Е. Степень вершины А здесь равна 2, вершин B и 

D - 3, С и Е – 1.

 

В неориентированных графах связи между вершинами симметричны, то  если есть связь между А и Б, то то она есть и между Б и А.

 

В ориентированных графах ребра представляют собой упорядоченные пары, здесь вершины, соединенные ребром, неравноправны. Это означает, что вершины, соединенные ребром, неравноправны. Одна из них называется начальной, а другая – конечной.  Ребро является исходящим для начальной вершины и входящим – для конечной. При описании ребра важен порядок вершин, при этом первой указывается начальная вершина.

 

На рис.3 дан пример ориентированного графа. В нем 6 вершин (А, Б, В, Г, Д, Е) и 8 ребер (АБ, АГ, АД, БГ, ВА, ДВ, ДЕ и ЕГ).

 

Путь в ориентированном графе – это последовательность ребер, в которой конечная вершина каждого ребра (кроме последнего) совпадает с начальной вершиной следующего ребра пути.

 

Путь проходит через вершину А, если вершина А является начальной для одного из ребер этого пути. Путь полностью определяется последовательностью вершин, через которые он проходит.

 

Начальная вершина первого ребра пути называется начальной вершиной пути, а конечная вершина последнего ребра пути – конечной вершиной пути. Путь называется циклом, если его начальная вершина совпадает с конечной.

 

Граф, в котором нет цикла, называется ациклическим. В таком графе всегда есть вершина, в которую не входит ни одно ребро (такая вершина называется источником), и вершина, из которой не выходит ни одно ребро (такая вершина называется стоком).

 

Графы, рассмотренные выше, показывали только связь между вершинами. Но также существуют графы, отражающие свойства связей (например, длину пути или стоимость проезда).  Чтобы отразить свойства связи, на ребрах ставят пометки, которые могут быть числами (как положительными, так и отрицательными), так и нечисловыми. Такие графы называются взвешенными.

 

Мы рассматриваем только графы, веса которых – целые неотрицательные числа.

 

Весом пути называется сумма путей ребер, образующих этот путь.

 

На рис.4 приведен пример взвешенного графа. Обратите внимание, что длины ребер не связаны с их весами (например, длина ребра АД  больше, чем БГ, но вес ребра АД меньше, чем ребра БГ).

 

Следует помнить, что веса ребер – это вовсе не длины отрезков на плоскости. Для них не обязательно соблюдать известное из математики неравенство треугольника. Например, в графе на рис.4  вес пути АБГ (2+8=10) меньше, чем вес ребра АГ (12).

 

Взвешенные графы удобно записывать в виде таблицы, которую называют весовой матрицей.

Весовая матрица – это квадратная таблица, в которой отражены все сведения о графе и весах его ребер.

 

Общее правило заполнения матрицы таково:

Каждая клетка матрицы соответствует паре вершин, расположенных в соответствующей строке и соответствующем столбце. Если две вершины графа Х и Y соединены ребром, то в клетку матрицы на пересечении строки Х и столбца Y, заносится вес ребра ХY, иначе клетка остается пустой.

 

Весовая матрица для неориентированного взвешенного графа всегда симметрична главной диагонали. Для ориентированных взвешенных графов это свойство чаще всего не выполняется.

 

Одна из важнейших задач, возникающих при анализе графов – это поиск минимального пути между двумя заданными вершинами, то есть имеет наименьший вес среди всех возможных путей между заданными вершинами.

 

Например, для транспортных графов, в которых ребра соответствуют дорогам, в зависимости от смысла весов минимальный путь может означать как путь наименьшей длины, так и путь с наименьшей стоимостью проезда, или путь с наименьшим возможным временем проезда  и т.п.

 

Для небольших графов минимальный путь можно найти, просмотрев все возможные пути.

 

Задача 1. 

Между населенными пунктами А, B, C, D, Е построены дороги, протяженность которых приведена в таблице (рис.6, а). Отсутствие числа в таблице означает, что прямой дороги между населенными пунктами нет. Определите длину кратчайшего пути между пунктами А и Е, если передвигаться можно только по построенным дорогам.,

Решение.

Данную таблицу можно рассматривать как весовую матрицу. Построим граф, соответствующий этой весовой матрице (рис.6, б).

В вершину Е ведет только один путь – из вершины С. Следовательно, для получения ответа нужно найти кратчайший путь из А в С и прибавить к нему длину пути СЕ.

Кратчайший путь из А в С – это путь АВС , который равен 3. Тогда искомый путь АЕ будет равен 3+2=5.

Ответ: 5

 

Задача 2.

Между населенными пунктами А, B, C, D, E построены дороги, протяженность которых приведена в таблице:

Определите кратчайший путь между пунктами А и Е (при условии, что двигаться можно только по построенным дорогам).

Решение.

Нарисуем граф, соответствующий в таблице.

Из него видно, что самый короткий путь – АDЕ = 5.

Ответ: 5

 

Задача 3.

Между населёнными пунктами A, B, C, D, E, F  построены дороги, протяжённость которых (в километрах) приведена в таблице. Определите длину кратчайшего пути между пунктами A и F, проходящий через Е.

Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Решение.

Нарисуем граф, соответствующий в таблице.

Из него видно, что самый короткий путь ABDEF = 14

Ответ: 14